# -*- coding: utf-8 -*-

"""剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。"""


class Token():
    def __init__(self, value, is_dot, has_star):
        self.value = value
        self.is_dot = is_dot
        self.has_star = has_star

    @staticmethod
    def parse(p):
        tokens = []

        i = 0
        while i < len(p):
            if p[i] == '.':
                value = None
                is_dot = True
            else:
                value = p[i]
                is_dot = False

            if i+1 < len(p) and p[i+1] == '*':
                has_star = True
                i += 1
            else:
                has_star = False

            tokens.append(Token(value, is_dot, has_star))
            i += 1

        return tokens

class Solution:
    """先分词，将模式字符串分为一个token序列，每个token有值，是否为dot，是否含star三个属性
    目标字符串和token序列各一个指针
    当前指针对得字符和token匹配后，选择下一个字符可以与哪些token匹配：
        如果当前token含有star，那么还可以与当前token匹配
        移动到下一个token
        如果该token含有star，那么可以继续往后移token，依次匹配含star得连续token，直到遇到一个不含star的token

    字符串和token序列前后维护哨兵，减少判断的逻辑。
    维护一个非本地success，如果最后全匹配成功，则将此success置为真。
    """
    def isMatch(self, s: str, p: str) -> bool:
        s = '^'+s+'$'
        tokens = Token.parse('^'+p+'$')

        # for token in tokens:
        #     print('value: %s, is_dot: %s, has_star: %s' % (token.value, token.is_dot, token.has_star))

        success = False

        def do(si, pi):
            nonlocal success

            if si == len(s) or pi == len(tokens):
                return

            # print(si, pi, s[si], tokens[pi].value)
            if s[si] == '$' and tokens[pi].value == '$':
                success = True
                return

            if (not tokens[pi].is_dot) and s[si] != tokens[pi].value:
                return

            x = pi
            if tokens[x].has_star:
                do(si+1, x)
            x += 1

            while True:
                if tokens[x].has_star:
                    do(si+1, x)
                    x += 1
                else:
                    do(si+1, x)
                    break

        do(0, 0)

        return success


if __name__ == '__main__':
    print(Solution().isMatch('aa', 'a'))
    print(Solution().isMatch('aa', 'a*'))
    print(Solution().isMatch('ab', '.*'))
    print(Solution().isMatch('aab', 'c*a*b'))
    print(Solution().isMatch('mississippi', 'mis*is*p*.'))

